package Hash表.两个数组的交集_349;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/*
给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以不考虑输出结果的顺序 。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

使用数组来做哈希的题目，是因为题目都限制了数值的大小
思路：

*/
public class Solution {
    public static void main(String[] args) {
        int[] nums1 = {4,7,9,7,6,7};
        int[] nums2 = {5,0,0,6,1,6,2,2,4};
        int[] end = intersection(nums1, nums2);
        for(int i = 0; i < end.length; i ++){
            System.out.println(end[i]);
        }
    }
    public static int[] intersection(int[] nums1, int[] nums2) {
        int[] temp = nums1;
        Arrays.sort(temp);
        // 记录nums1的最大值
        int max = temp[temp.length - 1];
        int num = 0;
        int[] hash = new int[1001];
        for (int i = 0; i < nums1.length; i ++){
            hash[nums1[i]] = 1;  // 所有出现的数字会在hash表中置为1
        }
        for (int i = 0; i < nums2.length; i ++){
            if (hash[nums2[i]] != 0)
            hash[nums2[i]] ++;
        }
        for (int i = 0; i <= max; i ++){
            if (hash[i] != 0 && hash[i] != 1){
                num ++;
            }
        }
        int[] end = new int[num];
        int j = 0;
        for (int i = 0; i <= max; i ++){
            if (hash[i] != 0 && hash[i] != 1){
                end[j ++] = i;
            }
        }
        return end;
    }
        // 方法2，用hashset 由于无序且不重复，可以用该方法
        public static int[] intersection1(int[] nums1, int[] nums2) {
            if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
                return new int[0];
            }
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> resSet = new HashSet<>();
            //遍历数组1
            for (int i : nums1) {
                set1.add(i);
            }
            //遍历数组2的过程中判断哈希表中是否存在该元素
            for (int i : nums2) {
                if (set1.contains(i)) {
                    resSet.add(i);
                }
            }

            //方法1：将结果集合转为数组

//            return resSet.stream().mapToInt(x -> x).toArray();

            //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
            int[] arr = new int[resSet.size()];
            int j = 0;
            for(int i : resSet){
                arr[j++] = i;
            }

            return arr;
        }

}
